#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> jug(n, vector<bool>(n));
        for (int i = 1; i < n; i++)
            for (int j = 0; j <= i; j++)
                if (s[i] == s[j])
                    jug[i][j] = i <= j + 1 ? true : jug[i - 1][j + 1];
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++)
        {
            dp[i] = i + 1;
            if (jug[i][0])
                dp[i] = 0;
            else
                for (int j = i; j > 0; j--)
                    if (jug[i][j])
                        dp[i] = min(dp[i], 1 + dp[j - 1]);
        }
        return dp[n - 1];
    }
};